// Copyright 2010 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// This file implements binary search.

// package sort -- go2cs converted at 2020 October 09 04:49:14 UTC
// import "sort" ==> using sort = go.sort_package
// Original source: C:\Go\src\sort\search.go

using System;

// TODO: This type of per-package type alias import may be needed during conversion for each import
#region [ import sort package type aliases ]

using IntSlice = go.slice<nint>;
using Float64Slice = go.slice<double>;
using StringSlice = go.slice<go.@string>;

#endregion

namespace go;

public static partial class sort_package
{
    // Search uses binary search to find and return the smallest index i
    // in [0, n) at which f(i) is true, assuming that on the range [0, n),
    // f(i) == true implies f(i+1) == true. That is, Search requires that
    // f is false for some (possibly empty) prefix of the input range [0, n)
    // and then true for the (possibly empty) remainder; Search returns
    // the first true index. If there is no such index, Search returns n.
    // (Note that the "not found" return value is not -1 as in, for instance,
    // strings.Index.)
    // Search calls f(i) only for i in the range [0, n).
    //
    // A common use of Search is to find the index i for a value x in
    // a sorted, indexable data structure such as an array or slice.
    // In this case, the argument f, typically a closure, captures the value
    // to be searched for, and how the data structure is indexed and
    // ordered.
    //
    // For instance, given a slice data sorted in ascending order,
    // the call Search(len(data), func(i int) bool { return data[i] >= 23 })
    // returns the smallest index i such that data[i] >= 23. If the caller
    // wants to find whether 23 is in the slice, it must test data[i] == 23
    // separately.
    //
    // Searching data sorted in descending order would use the <=
    // operator instead of the >= operator.
    //
    // To complete the example above, the following code tries to find the value
    // x in an integer slice data sorted in ascending order:
    //
    //    x := 23
    //    i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
    //    if i < len(data) && data[i] == x {
    //        // x is present at data[i]
    //    } else {
    //        // x is not present in data,
    //        // but i is the index where it would be inserted.
    //    }
    //
    // As a more whimsical example, this program guesses your number:
    //
    //    func GuessingGame() {
    //        var s string
    //        fmt.Printf("Pick an integer from 0 to 100.\n")
    //        answer := sort.Search(100, func(i int) bool {
    //            fmt.Printf("Is your number <= %d? ", i)
    //            fmt.Scanf("%s", &s)
    //            return s != "" && s[0] == 'y'
    //        })
    //        fmt.Printf("Your number is %d.\n", answer)
    //    }
    //
    public static nint Search(nint n, Func<nint, bool> f)
    { 
        // Define f(-1) == false and f(n) == true.
        // Invariant: f(i-1) == false, f(j) == true.
        nint i = 0;
        var j = n;
        while (i < j)
        {
            var h = (nint)((nuint)(i + j) >> 1); // avoid overflow when computing h
            // i ≤ h < j
            if (!f(h))
            {
                i = h + 1; // preserves f(i-1) == false
            }
            else
            {
                j = h; // preserves f(j) == true
            }
        } 
        // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
        return i;
    }

    // Convenience wrappers for common cases.

    // SearchInts searches for x in a sorted slice of ints and returns the index
    // as specified by Search. The return value is the index to insert x if x is
    // not present (it could be len(a)).
    // The slice must be sorted in ascending order.
    //
    public static nint SearchInts(slice<nint> a, nint x)
    {
        return Search(len(a), i => a[i] >= x);
    }

    // SearchFloat64s searches for x in a sorted slice of float64s and returns the index
    // as specified by Search. The return value is the index to insert x if x is not
    // present (it could be len(a)).
    // The slice must be sorted in ascending order.
    //
    public static nint SearchFloat64s(slice<double> a, double x)
    {
        return Search(len(a), i => a[i] >= x);
    }

    // SearchStrings searches for x in a sorted slice of strings and returns the index
    // as specified by Search. The return value is the index to insert x if x is not
    // present (it could be len(a)).
    // The slice must be sorted in ascending order.
    //
    public static nint SearchStrings(slice<@string> a, @string x)
    {
        return Search(len(a), i => a[i] >= x);
    }

    // Search returns the result of applying SearchInts to the receiver and x.
    public static nint Search(this IntSlice p, nint x)
    {
        return SearchInts(p, x);
    }

    // Search returns the result of applying SearchFloat64s to the receiver and x.
    public static nint Search(this Float64Slice p, double x)
    {
        return SearchFloat64s(p, x);
    }

    // Search returns the result of applying SearchStrings to the receiver and x.
    public static nint Search(this StringSlice p, @string x)
    {
        return SearchStrings(p, x);
    }
}
